#ifndef __DYNAMICARRAY_H_
#define __DYNAMICARRAY_H_
#include <stddef.h>
#include <cmath>
#include <limits.h>
#include <iostream>
#include <ostream>

namespace DARRAY
{

template<typename T>
class DynamicArray
{
public:
    DynamicArray(size_t capacity = 15):size(0),capacity(capacity)
    {
        array = new T[capacity];
    }
    DynamicArray(const DynamicArray& a)
    {   
        size = a.size;
        capacity = a.capacity;
        array = new T[capacity];
        for(size_t i = 0; i < size; i++)
        {
            array[i] = a.array[i];
        }
    }
    DynamicArray& operator=(const DynamicArray& a)
    {
        delete []array;
        size = a.size;
        capacity = a.capacity;
        array = new T[capacity];
        for(size_t i=0;i<size;i++)
        {
            array[i] = a.array[i];
        }
        return *this;
    }
    ~DynamicArray()
    {
         delete []array;
    }

    size_t Size()
    {
        return size;
    }

    void ReSize(size_t capacity) //扩容接口
    {
        this->capacity = capacity;
        this->size = (size > capacity) ? capacity : size;
        T *newP = new T[capacity];
        for(size_t i = 0; i < size; i++)
        {
        newP[i] = array[i];
        }
        delete []array;
        array = newP;
    }

    void InsertTail(const T& element)//尾部插入
    {
        if(size >= capacity)
        {
            ReSize(2 * capacity);
        }
        array[size++] = element; //时间复杂度O(1)
    }

    void InsertHead(const T& element)//头部插入
    {
        if(size >= capacity)
        {
            ReSize(2 * capacity);
        }
        for(size_t i = size; i > 0; i--) //时间复杂度O(n)
        {
            array[i] = array[i-1];
        }
        array[0] = element;
        size++;
    }

    void InsertByIndex(int index,const T& element)//中间插入
    {
        if(index < 0 || index > size) //排除非法位置
        {
            return;
        }

        if(size >= capacity)
        {
            ReSize(2 * capacity);
        }

        for(size_t i = size; i > index; i--) //时间复杂度O(n)
        {
            array[i] = array[i-1];
        }
        array[index] = element;
        size++;
    }

    void RemoveByIndex(int index)//按位置删除
    {
        if(index < 0 || index >= size) //排除非法位置
        {
            return;
        }

        for(size_t i = index; i < size - 1; i++) // 时间复杂度O(n)
        {
            array[i] = array[i+1];
        }
        size--;
    }

    void RemoveByElement(const T& element)//按值删除
    {
        for(int i = 0; i < size; i++) //时间复杂度 O(n^2)
        {
            if(array[i] == element)
            {
                RemoveByIndex(i);
                i--; // 删除多个相同的数
            }
        }
    }

    T* FindByIndex(int index) //按位置查找,通过返回地址查找
    {
        if(index < 0 || index > size) //排除非法位置，判断指针是否为空
        {
            return nullptr; 
        }
        return &array[index];  //时间复杂度 
    }

    DynamicArray<T> FindByElement(const T& element)//按值查找,返回的是数组，因为找到的值不止一个
    {
        DynamicArray<T> result;
        for(int i = 0; i < size; i++) //时间复杂度 O(n)
        {
            if(array[i] == element) 
            {
                result.InsertTail(i);
            }
        }
        return result;
    }
    
    void UpdateByIndex(int index,const T& element)//按位置修改
    {
        if(index < 0 || index > size) //排除非法位置
        {
            return;
        }
        array[index] = element;
    }

    void UpdateByElement(const T& oldValue,const T& newValue)//按值修改
    {
        for(int i = 0; i < size; i++) //时间复杂度 O(n)
        {
            if(array[i] == oldValue) 
            {
                array[i] = newValue;
            }
        }
    }

    void Sort()//排序
    {
        FastSort(0,size-1,0,2*log2(size));
    }

    void Duplicaye()//去重算法
    {
        for(int i = 1; i < size; i++) //时间复杂度O(n)
        {
            if(array[i] == array[i-1])
            {
                RemoveByIndex(i);
                i--;
            }
        }
    }

    DynamicArray Merge(const DynamicArray& a)//归并排序:合并两个已经有序的数列
    {
        size_t first = 0; //当前数组
        size_t second = 0; //传进来的数组
        DynamicArray result;
        //遍历两个数组都没有到结尾
        while(first < this->size && second < a.size)
        {
            if(this->array[first] <= a.array[second])
            {
                result.InsertTail(array[first++]);
            }
            else
            {
                result.InsertTail(a.array[second++]);
            }
        }
        while(first < this->size)
        {
            result.InsertTail(array[first++]);
        }
        while(second < a.size)
        {
            result.InsertTail(a.array[second++]);
        }
        return result;

    }

    DynamicArray FindInterSctn(const DynamicArray& a)//找交集
    {
        DynamicArray result;
        size_t first = 0;
        size_t second = 0;
        while(first < size && second < a.size)
        {
            if(array[first] == a.array[second])
            {
                result.InsertTail(array[first++]);
                second++;
            }
            else if(array[first] > a.array[second])
            {
                second++;
            }
            else
            {
                first++;
            }
        }
        return result;
    }

    DynamicArray FindUnionSet(const DynamicArray& a)//找并集
    {
        DynamicArray result;
        size_t first = 0;
        size_t second = 0;
        while(first < size && second < a.size)
        {
            if(array[first] == a.array[second])
            {
                result.InsertTail(array[first++]);
                second++;
            }
            else if(array[first] > a.array[second])
            {
                result.InsertTail(array[second++]);
            }
            else
            {
                result.InsertTail(array[first++]);
            }
            }
            while(first < this->size)
            {
                result.InsertTail(array[first++]);
            }
            while(second < a.size)
            {
                result.InsertTail(a.array[second++]);
            }
            return result;
    }

    DynamicArray FindDirfference(const DynamicArray& a) //找补集
    {
        DynamicArray result;
        size_t first = 0;
        size_t second = 0;
        while(first < size && second < a.size)
        {
        if(array[first] == a.array[second])
        {
            first++;
            second++;
        }
        else if(array[first] > a.array[second])
        {
            result.InsertTail(array[second++]);
        }
        else
        {
            result.InsertTail(array[first++]);
        }
        }
        while(first < this->size)
        {
            result.InsertTail(array[first++]);
        }
        while(second < a.size)
        {
            result.InsertTail(a.array[second++]);
        }
        return result;
    }

    bool operator==(const DynamicArray& a)//判断两个数列是否相等
    {
        if(a.size != size)
        {
            return false;
        }
        size_t first = 0;
        size_t second = 0;
        while(first < size && second < a.size)
        {
            if(array[first] == a.array[second])
            {
            first++;
            second++;
            }
            else
            {
                return false;
            }
        }
        return true;
    }

    size_t BinarySearch(const T& element)//二分查找
    {
        int left = 0;
        int right = size - 1;
        while(left <= right)
        {
            size_t mid = (left & right) + ((left^right) >> 1);
            if(array[mid] > element)
            {
                if(mid == 0)
                {
                    return ULONG_MAX;
                }
                right = mid - 1;
            }
            else if(array[mid] < element)
            {
                left = mid + 1;
            }
            else
            {
                return mid;
            }
        }
        return ULONG_MAX;

    }

    bool IsChild(const DynamicArray& a)//查找一个数列是不是子数列
    {
        int j = 0;
        for(int i = 0; i < size; i++) // O(n)
        {
            if(array[i] == a.array[j])
            {
                j++;
            }
        }
        return j == a.size;
    }

    bool IsCntnsChild(const DynamicArray& a)//查找连续子序列
    {
        for(int i = 0; i <= size - a.size; i++) // O(n^2)
        {
            if(subsequence(i,a.size) == a)
            {
                return true;
            }
        }
        return false;
    }

    DynamicArray subsequence(int index,size_t size)//切割获取子序列a
    {
        if(index < 0 || index + size > this->size)
        {
            return DynamicArray();
        }
        DynamicArray result;
        for(int i = index; i < index + size; i++)
        {
            result.InsertTail(array[i]);
        }
        return result;
    }

    void show()
    {
        for(int i = 0; i < size; i++)
        {
            std::cout<<array[i]<<" ";
        }
        std::cout<<std::endl;
    }
private:
    void FastSort(size_t start,size_t end,size_t deepth,size_t MaxDepth) //快速排序
    {
        if(start >= end)
        {
            return;
        }
        //如果超过了最大深度
        if(deepth > MaxDepth)
        {
            InsertSort(start,end); //换成插入排序
        }
        else//没超过最大深度就继续分组
        {
            size_t par = Partition(start,end);
                if(par != 0)
            FastSort(start,par-1,deepth+1,MaxDepth);
            FastSort(par+1,end,deepth+1,MaxDepth);
        }
    }
    void InsertSort(size_t start,size_t end) //插入排序
    {
        for (size_t i = start; i <= end; i++)
        {
            size_t j = i; 
            T temp = array[i]; 
            for(; j > start; j--) 
            {
                if(array[j-1] > temp)
                {
                    array[j] = array[j-1];
                }
                else
                {
                    break;
                }
            }
            array[j] = temp;
        }
    }

    size_t Partition(size_t start,size_t end) //分组函数
    {
        size_t left = start;
        size_t right = end;
        T temp = array[left];
        while(left < right)
        {
            while(left < right && array[right]>temp)
            {
                right--;
            }
            if(left < right)
            {
                array[left++] = array[right];
            }
            while(left < right && array[left]<temp)
            {
                left++;
            }
            if(left < right)
            {
                array[right--] = array[left];
            }
        }
        array[left] = temp;
        return left;
    }

    T *array;
    size_t capacity;
    size_t size;
    void (*freeptr)(T); // 专门用来进行数组元素释放的指针
    void (*PrintPtr)(T); //打印元素的函数指针
    bool (*SortPtr)(T,T); //排序指针
    bool (*equalPtr)(T,T); //比较指针
};

template <typename T>
inline std::ostream& operator<<(std::ostream &os, const DynamicArray<T> &list)
{   
    //typename声明后面跟随的模板是一个类型
    typename DynamicArray<T>:: Node *travelPoint = list.head->next; 
    while(travelPoint != nullptr) 
    {
        std::cout<<travelPoint->data<<" "; 
        travelPoint = travelPoint->next;
    }
    std::cout<<std::endl;
    return os;
}

}

#endif